package 力扣;

/**
 * @author yyq
 * @create 2022-06-19 15:15
 */
public class leetcode494 {
    int sum = 0;
    int method = 0;


    public static void main(String[] args) {
        leetcode494 leetcode494=new leetcode494();
        System.out.println(leetcode494.findTargetSumWays(new int[]{1,1,0,0,1}, 1));
    }
    public int findTargetSumWays(int[] nums, int target) {
        int zeroCount = 0;
        for (int i=0;i<nums.length;i++){
            if(nums[i]==0)
                zeroCount++;
            sum = sum + nums[i];
        }
        
        int startIndex = 0;
        backTracking(startIndex,nums,target);
        return (int) (method*Math.pow(2,zeroCount));
    }

    private void backTracking(int startIndex, int[] nums, int target) {
        if(sum==target){
            method++;
            return;
        }
        for (int i=startIndex;i<nums.length;i++){
            if(nums[i]==0) continue;
            if(sum-(nums[i]*2)<target){
                continue;
            }
            sum = sum - (nums[i]*2);
            backTracking(i+1,nums,target);
            sum = sum + (nums[i]*2);
        }
    }
}
